package pack1;

public class Demo2 {
    public static void main(String[] args) {

    }

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int row=obstacleGrid.length;
        int col=obstacleGrid.length;
        //起点为障碍物或终点为障碍物都为"没有路径"
        if(obstacleGrid[0][0]==1||obstacleGrid[row-1][col-1]==1)return 0;

        //1.定义dp数组(dp[i][j]含义为从起点到该节点共有几条路径)
        int[][]dp=new int[row][col];

        //2.初始化dp数组(由于状态转移需要从上推导，和从左推导，所以第一行和第一列都要初始化为1)
        //可以这么理解，除了第一行和第一列dp[][]元素路径都为1外，其他节点从起点到节点都需要知道
        //上一个节点和左一个节点的路径数，所以要先初始化(第一行和第一列)
        for(int i=0;i<row;i++){
            if(obstacleGrid[i][0]==1){
                break;
            }
            dp[i][0]=1;
        }

        for(int j=0;j<col;j++){
            if(obstacleGrid[0][j]==1){
                break;
            }
            dp[0][j]=1;
        }

        //状态转移
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }

        return dp[row-1][col-1];
    }

}
